package leetcode.code0367;

import java.util.TreeMap;

public class Solution2 extends Solution367 {

	private static int[] part = new int[] { 1, 1_00, 1_00_00, 1_00_00_00, 1_00_00_00_00 };

	private static TreeMap<Integer, Integer> base;

	static {
		base = new TreeMap<>();
		for (int i = 1; i < 10; i++) {
			base.put(i * i, i);
		}
	}

	@Override
	public boolean isPerfectSquare(int num) {
		int n = num;
		int index = this.index(n);// 找到高位
		int ans = 0; // 开根结果
		int[] res = new int[] { 0, 0 };
		int head = 0;
		for (int i = index; i >= 0; i--) {
			head = n / part[i] + res[1] * 100; // 待尝试部分 + 上次余数补足前两位
			res = this.tryHead(head, ans * 20);// 从答案的20被开始尝试 res[0]结果,res[1]余数
			ans = ans * 10 + res[0];// 尝试结果添加到结果中
			n %= part[i];
		}
		return res[1] == 0;// 最终余0 说明完全开根
	}

	private int[] tryHead(int head, int div) {
		int ans1 = 0;
		int ans2 = 0;
		if (div == 0) {
			ans1 = base.floorKey(head);
			ans2 = head - ans1;
		} else {
			int d = head / div;
			while (true) {
				int tryTo = div + d;
				int mul = 0;
				if ((mul = tryTo * d) <= head) {
					return new int[] { d, head - mul };
				} else {
					d--;
				}
			}
		}
		return new int[] { base.get(ans1), ans2 };
	}

	private int index(int num) {
		for (int i = part.length - 1; i >= 0; i--) {
			if (num / part[i] > 0) {
				return i;
			}
		}
		return 0;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug4();
		so.debug3();
		so.debug1();
		so.debug2();
//		System.out.println(so.isPerfectSquare(255));
//		System.out.println(so.isPerfectSquare(256));
//		System.out.println(so.isPerfectSquare(1024));
//		System.out.println(so.isPerfectSquare(1025));
//		System.out.println(Math.sqrt(255));
	}

}
